package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 147. 对链表进行插入排序
 * @date 2025/6/5 11:53
 */
public class E147 {

    /**
     * 思路：插入排序
     *
     * @param head 头节点
     * @return 排好序的链表头节点
     */
    public ListNode insertionSortList1(ListNode head) {
        if (head == null) return null;
        int length = 0;
        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }
        curr = head.next;
        ListNode sentinel = new ListNode();
        sentinel.next = head;
        head.next = null; // 注意这里需要断开已经排好的尾节点
        for (int i = 0; i < length - 1; i++) {
            ListNode next = curr.next;
            ListNode p = sentinel.next;
            ListNode prev = sentinel;
            while (p != null && p.val < curr.val) {
                prev = p;
                p = p.next;
            }
            prev.next = curr;
            curr.next = p;
            curr = next;
        }
        return sentinel.next;
    }

    /**
     * 思路：插入排序，优化，考虑大部分已经排好序的情况
     *
     * @param head 头节点
     * @return 排好序的链表头节点
     */
    public ListNode insertionSortList2(ListNode head) {
        if (head == null) return null;
        int length = 0;
        ListNode curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }
        curr = head.next;
        ListNode sentinel = new ListNode();
        sentinel.next = head;
        head.next = null;
        ListNode last = sentinel.next;
        for (int i = 0; i < length - 1; i++) {
            ListNode next = curr.next;
            if (last.val < curr.val) {
                last.next = curr;
                curr.next = null;
                last = curr;
            } else {
                ListNode p = sentinel.next;
                ListNode prev = sentinel;
                while (p != null && p.val < curr.val) {
                    prev = p;
                    p = p.next;
                }
                prev.next = curr;
                curr.next = p;
            }
            curr = next;
        }
        return sentinel.next;
    }
}
